type rec lambda = 
  | Var(string)
  | Fn(string, lambda)
  | App(lambda, lambda)

let print_lambda = l => {
  let print_paren = (b, s) => {
    if b { "(" ++ s ++ ")" } else { s }
  }
  let rec go = (l, p) => {
    switch l {
      | Var(x) => x
      | Fn(x, a) => print_paren(p>0, "fun " ++ x ++ " -> " ++ go(a, 0))
      | App(a, b) => print_paren(p>1, go(a, 1) ++ " " ++ go(b, 2))

    }
  }
  go(l, 0)
}

// Homework: implement the substitution
let rec subst = (x, v, a) => {
  assert false
}

let rec eval1 = (t: lambda) => {
  switch t {
  | Var(_) => assert false
  | Fn(_, _) => t
  | App(f, arg) => {
    let Fn(x, body) = eval1(f)
    let va = eval1(arg)
      eval1(subst(x, va, body))
    }
  }
}

type rec value = Vclosure (env, string, lambda)
and env = list<(string, value)>

let eval2 = (t: lambda) => {
  let rec go = (e, t) => {
    switch t {
    | Var(x) => List.assoc(x, e)
    | Fn(x, body) => Vclosure(e, x, body)
    | App(f, arg) => {
      let Vclosure(e', x, body) = go(e, f)
      let va = go(e, arg)
        go(list{(x, va), ...e'}, body)
      }
    }
  }
  go (list{}, t)
}